#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
/**
 * Definition for singly-linked list.
 */

typedef struct ListNode ListNode;
typedef ListNode* ElementType;

struct ListNode {
      int val;
      struct ListNode *next;
};

typedef struct QueueNode QueueNode;
struct QueueNode {
    ElementType elm;
    struct QueueNode *next;
    struct QueueNode *tail;
};

QueueNode *queueInit();
bool queueEmpty(QueueNode*);
void enQueue(QueueNode*,ElementType);
ElementType deQueue(QueueNode*);

ListNode * mergeTwoLists(ListNode *list1,ListNode *list2){
    ListNode *head=NULL;
    ListNode **h=&head;
    while( list1 && list2 ){
        if( list1->val < list2->val ){
            *h=list1;
            list1=list1->next;
        }
        else{
            *h=list2;
            list2=list2->next;
        }
        h=&((*h)->next);
    }
    if( list1 )
        *h=list1;
    if( list2 )
        *h=list2;
    return head;
}
/*
void prtL(ListNode* l){
    printf("-------------------\n");
    while (l){
        printf("->%d",l->val);
        l=l->next;
    }
    printf("\n-------------------\n");
    return;
}*/

struct ListNode* mergeKLists(struct ListNode** lists, int listsSize) {
    QueueNode *q=queueInit();
    for( int i=0; i<listsSize; i++ ){
        enQueue(q,lists[i]);
    }
    ListNode *l1=NULL,*l2=NULL,*r=NULL;
    while( !queueEmpty(q) ){
        l1=deQueue(q);
        if( queueEmpty(q) ){
            r=l1;
            break;
        }
        l2=deQueue(q);
        r=mergeTwoLists(l1,l2);
prtL(r);
        enQueue(q,r);
    }
    return r;
}

QueueNode *queueInit(){
    QueueNode *r=malloc(sizeof(QueueNode));
    r->next=NULL;
    r->tail=r;
    return r;
}
bool queueEmpty(QueueNode* q){
    return (q->next==NULL);
}

void enQueue(QueueNode* q,ElementType e){
    QueueNode *new=malloc(sizeof(QueueNode));
    new->elm=e;
    new->next=NULL;
    q->tail->next=new;
    q->tail=new;
    return;
}
ElementType deQueue(QueueNode* q){
    QueueNode *tmp=q->next;
    ElementType r=tmp->elm;
    q->next=tmp->next;
    free(tmp);
    if( !q->next )
        q->tail=q;
    return r;
}
int main(){
    ListNode n1,n2,n3,n4;
    n1.val=1;
    n2.val=2;
    n3.val=34;
    n4.val=400;
    n1.next=&n2;
    n2.next=&n3;
    n3.next=&n4;
    n4.next=NULL;
    ListNode *l1=&n1;
    ListNode t1,t2,t3,t4;
    t1.val=5;
    t2.val=8;
    t3.val=13;
    t4.val=63;
    t1.next=&t2;
    t2.next=&t3;
    t3.next=&t4;
    t4.next=NULL;
    ListNode *l2=&t1;

    ListNode x1,x2,x3,x4;
    x1.val=50;
    x2.val=83;
    x3.val=133;
    x4.val=653;
    x1.next=&x2;
    x2.next=&x3;
    x3.next=&x4;
    x4.next=NULL;
    ListNode *l3=&x1;

    ListNode *lists[3]={l1,l2,l3};
    ListNode* l=mergeKLists(lists,3);
    while ( l ){
        printf(" -->%d",l->val);
        l=l->next;
    }
    return 0;
}
